'''
https://leetcode.cn/problems/reverse-pairs/
'''
from typing import List


class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        if not nums: return 0

        def numOfReversePairs(l, r):
            if l >= r: return 0
            mid = (l + r) // 2
            return numOfReversePairs(l, mid) + numOfReversePairs(mid + 1, r) + merge(l, mid, r)

        def merge(l, m, r):
            # 倒序排序 and 统计结果
            ans = 0
            i, j = l, m + 1
            while i <= m:
                while j <= r and nums[i] <= 2 * nums[j]:
                    j += 1
                ans += r - j + 1
                i += 1
            help = [0] * (r - l + 1)
            i, j, k = l, m + 1, 0
            while i <= m and j <= r:
                if nums[i] >= nums[j]:
                    help[k] = nums[i]
                    i += 1
                else:
                    help[k] = nums[j]
                    j += 1
                k += 1
            help[k:] = nums[i:m + 1] if i <= m else nums[j:r + 1]
            nums[l:r + 1] = help[:]
            return ans

        return numOfReversePairs(0, len(nums) - 1)
